package a03_哈希;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * <p>
 * a09_四数之和复习4
 * </p>
 *
 * @author flyduck
 * @since 2024-12-29
 */
public class a09_四数之和复习4 {
    public static void main(String[] args) {
        a09_四数之和复习4 test = new a09_四数之和复习4();
        int[] nums = new int[]{1,0,-1,0,-2,2};
        test.fourSum(nums, 0);

    }
    public List<List<Integer>> fourSum(int[] nums, int target) {
        Arrays.sort(nums);
        List<List<Integer>> resultList = new ArrayList<>();
        outer1:for (int i = 0; i < nums.length; i++) {
            if(nums[i] > 0 && target > 0 && nums[i] > target){
               break outer1;
            }
            if(i > 0 && nums[i] == nums[i-1]){
                continue outer1;
            }
            outer2:for (int j = i + 1; j < nums.length; j++) {
                if(nums[i] + nums[j] > 0 && target > 0 && nums[i] + nums[j] > target){
                    break outer2;
                }
                if(j > (i+1) && nums[j] == nums[j-1]){
                    continue outer2;
                }

                int m = j + 1;
                int n = nums.length - 1;
                inner:while (m < n) {
                   if(m > (j+1) && nums[m] == nums[m-1]){
                       m++;
                       continue inner;
                   }
                   if(n < (nums.length - 1) && nums[n] == nums[n+1]){
                       n--;
                       continue inner;
                   }

                   long sum = (long)nums[i] + nums[j] + nums[m] + nums[n];
                   if(sum > target){
                       n--;
                   }else if(sum < target){
                       m++;
                   }else {
                       List<Integer> result = new ArrayList<>();
                       result.add(nums[i]);
                       result.add(nums[j]);
                       result.add(nums[m]);
                       result.add(nums[n]);
                       resultList.add(result);
                       m++;
                       n--;
                   }
                }
            }
        }
        return resultList;
    }
}
